"""
DSU: Disjoint Set Union，并查集
是一种高效处理集合合并与查询连通性的数据结构，常用于解决动态连通性问题。
"""

"""题目
朋友圈的数量
有n个人, 他们的编号从 0 到 n-1. 给定一个 n x n 的临界矩阵 m , 其中:
M[i][j] = 1, 表示第i个人和第j个人是朋友, M[i][j] = 0, 表示两人并不认识
如果 A 和 B 是朋友, 且 B 和 C 是朋友, 那么 A 和 C 也在一个朋友圈内.
请你统计总共有多少个互不关联的朋友圈(连通分量).
"""

"""分析
这道题的核心是连通分量的统计，十分契合并查集（Disjoint Set Union, DSU）结构：
1. 初始化
我们创建一个大小为 n 的并查集，每个人一开始都是单独的一组。
2. 遍历矩阵并合并
对于每对 (i,j)，如果 M[i][j] == 1，就将 i 和 j 在并查集中做一次 union(i, j) 操作。
注意对称矩阵，只需遍历上三角或下三角以免重复。
3. 统计根节点
最后，对每个 i∈[0,n) 调用 find(i) 找到它所属的根节点（代表元），把这些根节点放入一个集合去重，集合大小即为朋友圈数量。
"""


class DSU:
    def __init__(self, size: int):
        self.parent = list(range(size))  # 初始状态下每个元素的父节点都指向其自身
        self.rank = [0] * size

    def find(self, x):
        """find操作:查询元素属于哪个集合(查找根节点)"""
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # 路径压缩: 相同根节点的元素的父节点均直接指向其根节点, 降低树的高度
            x = self.parent[x]
        return x

    def union(self, x, y):
        """find操作:查询元素属于哪个集合(查找根节点)"""
        root_x = self.find(x)
        root_y = self.find(y)
        # 按秩合并: 按照树的大小合并(另一个选择是按照树的深度合并)
        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                root_x, root_y = root_y, root_x
            self.parent[root_y] = root_x
            self.rank[root_x] += self.rank[root_y]

    def size(self, idx):
        return self.rank[self.find(idx)]


def count_CC(M: list[list[int]]):
    n = len(M)
    dsu = DSU(n)
    for i in range(n):
        for j in range(i):
            if M[i][j] == 1:
                dsu.union(i, j)

    roots = {dsu.find(x) for x in range(n)}
    return len(roots)


if __name__ == '__main__':
    M = [[1, 0, 1, 0, 0],
         [0, 1, 0, 0, 1],
         [1, 0, 1, 0, 0],
         [0, 0, 0, 1, 0],
         [0, 1, 0, 0, 1],]
    print(count_CC(M))
